package code.c03_stackQueue.sqStack;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/10/2 20:05
 * @package code.c03_stackQueue.stack
 * @description 顺序栈
 */

public class SqStackClass<E> {
    final int INITCAPACITY = 10;
    private int capacity;
    private E[] data;
    private int top;

    public SqStackClass() {
        data = (E[]) new Object[INITCAPACITY];
        capacity = INITCAPACITY;
        top = -1;
    }

    private void updateCapacity(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < top; i++) {
            newData[i] = data[i];
            capacity = newCapacity;
            data = newData;
        }
    }

    // ================================ 顺序表的基本运算 ================================

    /**
     * 入栈
     * @return
     */
    public boolean empty() {
        return top == -1;
    }

    /**
     * 出栈
     * @param e
     */
    public void push(E e) {
        if (top == capacity - 1) {
            updateCapacity((top + 1) * 2);
        }
        // 入栈操作
        top++;
        data[top] = e;
    }

    /**
     * 取栈顶元素
     * @return
     */
    public E pop() {
        if (empty()) {
            throw new IllegalArgumentException("出栈：栈空");
        }
        E e = data[top];
        top--;
        if (capacity > INITCAPACITY && (top + 1) == (capacity / 4)) {
            updateCapacity(capacity /2);
        }
        return e;
    }

    public E peek(){
        if (empty()) {
            throw new IllegalArgumentException("取栈顶元素：栈空");
        }
        return data[top];
    }
}
